{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Language Processing Concepts\n",
    "### Original tutorial by Brain Lehman, with updates by Fiona Pigott\n",
    "\n",
    "The goal of this tutorial is to introduce a few basical vocabularies, ideas, and Python libraries for thinking about topic modeling, in order to make sure that we have a good set of vocabulary to talk more in-depth about processing languge with Python later. We'll spend some time on defining vocabulary for topic modeling and using basic topic modeling tools.\n",
    "\n",
    "A big thank-you to the good people at the Stanford NLP group, for their informative and helpful online book: https://nlp.stanford.edu/IR-book/.\n",
    "\n",
    "### Definitions.\n",
    "1. **Document**: a body of text (eg. tweet)\n",
    "2. **Tokenization**: dividing a document into pieces (and maybe throwing away some characters), in English this often (but not necessarily) means words separated by spaces and puctuation.\n",
    "3. **Text corpus**: the set of documents that contains the text for the analysis (eg. many tweets)\n",
    "4. **Stop words**: words that occur so frequently, or have so little topical meaning, that they are excluded (e.g., \"and\")\n",
    "5. **Vectorize**: Turn some documents into vectors\n",
    "6. **Vector corpus**: the set of documents transformed such that each token is a tuple (token_id , doc_freq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# first, get some text:\n",
    "import fileinput\n",
    "try:\n",
    "    import ujson as json\n",
    "except ImportError:\n",
    "    import json\n",
    "documents = []\n",
    "for line in fileinput.FileInput(\"example_tweets.json\"):\n",
    "    documents.append(json.loads(line)[\"text\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1) Document\n",
    "In the case of the text that we just imported, each entry in the list is a \"document\"--a single body of text, hopefully with some coherent meaning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"One document: \\\"{}\\\"\".format(documents[0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Tokenization\n",
    "We split each document into smaller pieces (\"tokens\") in a process called tokenization. Tokens can be counted, and most importantly, compared between documents. There are potentially many different ways to tokenize text--splitting on spaces, removing punctionation, diving the document into n-character pieces--anything that gives us tokens that we can, hopefully, effectively compare across documents and derive meaning from.\n",
    "\n",
    "Related to tokenization are processes called *stemming* and *lemmatiztion* which can help when using tokens to model topics based on the meaning of a word. In the phrases \"they run\" and \"he runs\" (space separated tokens: [\"they\", \"run\"] and [\"he\", \"runs\"]) the words \"run\" and \"run*s*\" mean basically the same thing, but are two different tokens. Stemming and/or lemmatization help us compare tokens with the same meaning but different spelling/suffixes.\n",
    "\n",
    "#### Lemmatization:\n",
    "Uses a dictionary of words and their possible morphologies to map many different forms of a base word (\"lemma\") to a single lemma, comparable across documents. E.g.: \"run\", \"ran\", \"runs\", and \"running\" might all map to the lemma \"run\"\n",
    "\n",
    "#### Stemming: \n",
    "Uses a set of heuristic rules to try to approximate lemmatization, without knowing the words in advance. For the English language, a simple and effective stemming algorithm might simply be to remove an \"s\" from the ends of words, or an \"ing\" from the end of words. E.g.: \"run\", \"runs\", and \"running\" all map to \"run,\" but \"ran\" (an irregularrly conjugated verb) would not. \n",
    "\n",
    "Stemming is particularly interesting and applicable in social data, because while some words are decidely *not* standard English, conventinoal rules of grammar still apply. A fan of the popular singer Justin Bieber might call herself a \"belieber,\" while a group of fans call themselves \"beliebers.\" You won't find \"belieber\" in any English lemmatization dictionary, but a good stemming algorithm will still map \"belieber\" and \"beliebers\" to the same token (\"belieber\", or even \"belieb\", if we remover the common suffix \"er\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from nltk.stem import porter\n",
    "from nltk.tokenize import TweetTokenizer\n",
    "\n",
    "# tokenize the documents\n",
    "# find good information on tokenization:\n",
    "# https://nlp.stanford.edu/IR-book/html/htmledition/tokenization-1.html\n",
    "# find documentation on pre-made tokenizers and options here:\n",
    "# http://www.nltk.org/api/nltk.tokenize.html\n",
    "tknzr = TweetTokenizer(reduce_len = True)\n",
    "\n",
    "# stem the documents\n",
    "# find good information on stemming and lemmatization:\n",
    "# https://nlp.stanford.edu/IR-book/html/htmledition/stemming-and-lemmatization-1.html\n",
    "# find documentation on available pre-implemented stemmers here:\n",
    "# http://www.nltk.org/api/nltk.stem.html\n",
    "stemmer = porter.PorterStemmer()\n",
    "for doc in documents[0:10]:\n",
    "    tokenized = tknzr.tokenize(doc)\n",
    "    stemmed = [stemmer.stem(x) for x in tokenized]\n",
    "    print(\"Original document:\\n{}\\nTokenized result:\\n{}\\nStemmed result:\\n{}\\n\".format(\n",
    "        doc, tokenized, stemmed))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Text corpus\n",
    "\n",
    "The text corpus is a collection of all of the documents (Tweets) that we're interested in modeling. Topic modeling and/or clustering on a corpus tends to work best if that corpus has some similar themes--this will mean that some tokens overlap, and we can get signal out of when documents share (or do not share) tokens. \n",
    "\n",
    "Modeling text tends to get much harder the more different, uncommon and unrelated tokens appear in a text, especially when we are working with social data, where tokens don't necessarily appear in a dictionary. This difficultly (of having many, many unrelated tokens as dimension in our model) is one example of the [curse of dimensionality](https://en.wikipedia.org/wiki/Curse_of_dimensionality)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of documents in the corpus\n",
    "print(\"There are {} documents in the corpus.\".format(len(documents)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4) Stop words:\n",
    "Stop words are simply tokens that we've chosen to remove from the corpus, for any reason. In English, removing words like \"and\", \"the\", \"a\", \"at\", and \"it\" are common choices for stop words. Stop words can also be edited per project requirement, in case some words are too common in a particular dataset to be meaningful (another way to do stop word removal is to simply remove any word that appears in more than some fixed percentage of documents)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.corpus import stopwords\n",
    "\n",
    "stopset = set(stopwords.words('english'))\n",
    "print(\"The English stop words list provided by NLTK: \")\n",
    "print(stopset)\n",
    "\n",
    "stopset.update([\"twitter\"]) # add token\n",
    "stopset.remove(\"i\")   # remove token\n",
    "print(\"\\nAdd or remove stop words form the set: \")\n",
    "print(stopset)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5) Vectorize:\n",
    "\n",
    "Transform each document into a vector. There are several good choices that you can make about how to do this transformation, and I'll talk about each of them in a second.\n",
    "\n",
    "In order to vectorize documents in a corpus (without any dimensional reduction around the vocabulary), think of each document as a row in a matrix, and each column as a word in the vocabulary of the entire corpus. In order to vectorize a corpus, we must read the entire corpus, assign one word to each column, and then turn each document into a row.\n",
    "\n",
    "**Example**:   \n",
    "**Documents**: \"I love cake\", \"I hate chocolate\", \"I love chocolate cake\", \"I love cake, but I hate chocolate cake\" \n",
    "**Stopwords**: Say, because the word \"but\" is a conjunction, we want to make it a stop word (not include it in our document vectors)\n",
    "**Vocabulary**: \"I\" (column 1), \"love\" (column 2), \"cake\" (column 3), \"hate\" (column 4), \"chocolate\" (column 5)\n",
    "\\begin{equation*}\n",
    "\\begin{matrix}\n",
    "\\text{\"I love cake\"  } & =\\\\\n",
    "\\text{\"I hate chocolate\" } & =\\\\\n",
    "\\text{\"I love chocolate cake\" } & = \\\\\n",
    "\\text{\"I love cake, but I hate chocolate cake\"} & =\n",
    "\\end{matrix}\n",
    "\\qquad\n",
    "\\begin{bmatrix}\n",
    "1 & 1 & 1 & 0 & 0\\\\\n",
    "1 & 0 & 0 & 1 & 1\\\\\n",
    "1 & 1 & 1 & 0 & 1\\\\\n",
    "2 & 1 & 2 & 1 & 1\n",
    "\\end{bmatrix}\n",
    "\\end{equation*}\n",
    "\n",
    "\n",
    "Vectorization like this don't take into account word order (we call this property \"bag of words\"), and in the above example I am simply counting the frequency of each term in each document."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# we're going to use the vectorizer functions that scikit learn provides\n",
    "\n",
    "# define the tokenizer that we want to use\n",
    "# must be a callable function that takes a document and returns a list of tokens\n",
    "tknzr = TweetTokenizer(reduce_len = True)\n",
    "stemmer = porter.PorterStemmer()\n",
    "def myTokenizer(doc):\n",
    "    return [stemmer.stem(x) for x in tknzr.tokenize(doc)]\n",
    "\n",
    "# choose the stopword set that we want to use\n",
    "stopset = set(stopwords.words('english'))\n",
    "stopset.update([\"http\",\"https\",\"twitter\",\"amp\"])\n",
    "\n",
    "# vectorize\n",
    "# we're using the scikit learn CountVectorizer function, which is very handy\n",
    "# documentation here: \n",
    "# http://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.CountVectorizer.html\n",
    "from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer\n",
    "vectorizer = CountVectorizer(tokenizer = myTokenizer, stop_words = stopset)\n",
    "vectorized_documents = vectorizer.fit_transform(documents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vectorized_documents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "_ = plt.hist(vectorized_documents.todense().sum(axis = 1))\n",
    "_ = plt.title(\"Number of tokens per document\")\n",
    "_ = plt.xlabel(\"Number of tokens\")\n",
    "_ = plt.ylabel(\"Number of documents with x tokens\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import logspace, ceil, histogram, array\n",
    "# get the token frequency\n",
    "token_freq = sorted(vectorized_documents.todense().astype(bool).sum(axis = 0).tolist()[0], reverse = False)\n",
    "# make a histogram with log scales\n",
    "bins = array([ceil(x) for x in logspace(0, 3, 5)])\n",
    "widths = (bins[1:] - bins[:-1])\n",
    "hist = histogram(token_freq, bins=bins)\n",
    "hist_norm = hist[0]/widths\n",
    "# plot (notice that most tokens only appear in one document)\n",
    "plt.bar(bins[:-1], hist_norm, widths)\n",
    "plt.xscale('log')\n",
    "plt.yscale('log')\n",
    "_ = plt.title(\"Number of documents in which each token appears\")\n",
    "_ = plt.xlabel(\"Number of documents\")\n",
    "_ = plt.ylabel(\"Number of tokens\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Bag of words\n",
    "Taking all the words from a document, and sticking them in a bag. Order does not matter, which could cause a problem. \"Alice loves cake\" might have a different meaning than \"Cake loves Alice.\"\n",
    "\n",
    "#### Frequency\n",
    "Counting the number of times a word appears in a document.\n",
    "\n",
    "#### Tf-Idf (term frequency inverse document frequency):\n",
    "A statistic that is intended to reflect how important a word is to a document in a collection or corpus. The Tf-Idf value increases proportionally to the number of times a word appears in the document and is inversely proportional to the frequency of the word in the corpus--this helps control words that are generally more common than others.  \n",
    "\n",
    "There are several different possibilities for computing the tf-idf statistic--choosing whether to normalize the vectors, choosing whether to use counts or the logarithm of counts, etc. I'm going to show how scikit-learn computed the tf-idf statistic by default, with more information available in the documentation of the sckit-learn [TfidfVectorizer](http://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.TfidfTransformer.html).\n",
    "\n",
    "$tf(t)$ : Term Frequency, count of the number of times each term appears in the document.  \n",
    "$idf(d,t)$ : Inverse document frequency.  \n",
    "$df(d,t)$ : Document frequency, the count of the number of documents in which the term appears. \n",
    "\n",
    "$$\n",
    "tfidf(t) = tf(t) * \\log\\big(\\frac{1 + n}{1 + df(d, t)}\\big) + 1\n",
    "$$\n",
    "\n",
    "We also then take the Euclidean ($l2$) norm of each document vector, so that long documents (documents with many non-stopword tokens) have the same norm as shorter documents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# documentation on this sckit-learn function here:\n",
    "# http://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.TfidfTransformer.html\n",
    "tfidf_vectorizer = TfidfVectorizer(tokenizer = myTokenizer, stop_words = stopset)\n",
    "tfidf_vectorized_documents = tfidf_vectorizer.fit_transform(documents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tfidf_vectorized_documents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# you can look at two vectors for the same document, from 2 different vectorizers:\n",
    "tfidf_vectorized_documents[0].todense().tolist()[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vectorized_documents[0].todense().tolist()[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## That's all for now!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
